package com.ctrip.demo.leetcode;

import java.util.ArrayList;
import java.util.List;

public class KuoHao {

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));

        System.out.println("大学费用---》" + (18000*4 + 7500*4) + "元，且前提不包括其它费用");
    }

    public static List<String> generateParenthesis(int n) {

        List<String> res = new ArrayList<>();
        generate(res, "", 0, 0, n);

        return res;

    }

    public static void generate(List<String> res, String ans, int count1, int count2, int n) {

        if (count1 > n || count2 > n) {
            return;
        }

        if (count1 == n && count2 == n) {
            res.add(ans);
        }

        if (count1 >= count2) {
            String ans1 = new String(ans);
            generate(res, ans + "(", count1 + 1, count2, n);
            generate(res, ans + ")", count1, count2 + 1, n);
        }


    }


//    public static void generate(List<String> res, String ans, int count1, int count2, int n) {
//
//        if (count1 > n || count2 > n) {
//            return;
//        }
//
//        if (count1 == n && count2 == n) {
//            res.add(ans);
//        }
//
//
//        if (count1 >= count2) {
//            String ans1 = new String(ans);
//            generate(res, ans + "(", count1 + 1, count2, n);
//            generate(res, ans1 + ")", count1, count2 + 1, n);
//
//        }
//    }


}
